package com.wc.fortnight_blue_bridge.Q231111.Q6280;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.StreamTokenizer;

/**
 * @Author congge
 * @Date 2023/11/11 22:26
 * 迷宫逃脱
 * https://www.lanqiao.cn/problems/6280/learning/?contest_id=146
 */
public class Main {
    public static void main(String[] args) {
        Input sc = new Input();
        int m = sc.nextInt();
        int n = sc.nextInt();
        int q = sc.nextInt();
        int[][] array = new int[m + 5][n + 5];
        /**
         * dp[i][j][k] 存储的是到达i j用了k把钥匙的最大值
         */
        long[][][] dp = new long[m + 5][n + 5][5];
        for (int i = 1; i <= m; i++) {
            for (int j = 1; j <= n; j++) {
                array[i][j] = sc.nextInt();
            }
        }
        for (int i = 1; i <= m; i++) {
            for (int j = 1; j <= n; j++) {
                for (int k = 0; k <= q; k++) {
                    dp[i][j][k] = Long.MIN_VALUE;
                }
            }
        }

        dp[1][1][0] = array[1][1];
        for (int i = 1; i <= m; i++) {
            for (int j = 1; j <= n; j++) {
                for (int k = 0; k <= q; k++) {
                    // 遍历左边
                    if (gcd(array[i][j], array[i][j + 1]) == 1) {
                        dp[i][j + 1][k + 1] = Math.max(dp[i][j + 1][k + 1], dp[i][j][k] + array[i][j + 1]);
                    } else {
                        dp[i][j + 1][k] = Math.max(dp[i][j + 1][k], dp[i][j][k] + array[i][j + 1]);
                    }
                    // 遍历上边
                    if (gcd(array[i][j], array[i + 1][j]) == 1) {
                        dp[i + 1][j][k + 1] = Math.max(dp[i + 1][j][k + 1], dp[i][j][k] + array[i + 1][j]);
                    } else {
                        dp[i + 1][j][k] = Math.max(dp[i + 1][j][k], dp[i][j][k] + array[i + 1][j]);
                    }
                }
            }
        }
        long ans = Long.MIN_VALUE;
        for (int i = 0; i <= q; i++) {
            ans = Math.max(ans, dp[m][n][i]);
        }
        if (ans <= 0){
            ans = -1;
        }
        System.out.println(ans);
    }

    /**
     * 计算最大公约数，判断是否是互质
     *
     * @param num1
     * @param num2
     * @return
     */
    public static long gcd(long num1, long num2) {
        if (num1 > num2) {
            return gcd(num2, num1);
        }
        if (num1 == 0) {
            return -1;
        }
        while (num2 % num1 != 0) {
            num2 = num2 % num1;
            num2 = num1 + num2;
            num1 = num2 - num1;
            num2 = num2 - num1;
        }

        return num1;
    }

    static class Input {
        StreamTokenizer in = new StreamTokenizer(new BufferedReader(new InputStreamReader(System.in)));

        public int nextInt() {
            try {
                in.nextToken();
            } catch (IOException e) {
                e.printStackTrace();
            }
            return (int) in.nval;
        }
    }

}
